package com.york.tinyrpc.protoss.loadbalancer;

import com.york.tinyrpc.protoss.model.ServiceMetaInfo;

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * 一致性哈希
 * 1. 解决传统哈希算法在节点变动时大规模重新映射的问题，通过虚拟节点实现更均匀的负载分布，保持相同请求始终路由到同一服务实例（对有状态服务友好）
 * 2. 虚拟节点环（TreeMap），使用TreeMap有序结构存储虚拟节点，每个真实节点生成100个虚拟节点（VIRTUAL_NODE_NUM）
 * 虚拟节点命名格式：服务地址+#+序号（如"192.168.1.1#0"）
 * 请求路由过程：
 * 计算请求参数的哈希值，使用ceilingEntry查找最近的虚拟节点，哈希环回绕机制（找不到时取首节点）
 */
public class ConsistentHashLoadBalancer implements LoadBalancer {

    /**
     * 一致性 Hash 环，存放虚拟节点
     */
    private final TreeMap<Integer, ServiceMetaInfo> virtualNodes = new TreeMap<>();

    /**
     * 虚拟节点数
     */
    private static final int VIRTUAL_NODE_NUM = 100;

    /**
     * 获取目标服务
     *
     * @param requestParams 请求参数，目前只有方法名，在一致性哈希中可以保证该方法会被映射到目标节点上
     * @param serviceList   可选服务列表
     * @return
     */
    @Override
    public ServiceMetaInfo getTargetService(Map<String, Object> requestParams, List<ServiceMetaInfo> serviceList) {
        if (serviceList.isEmpty()) {
            return null;
        }

        // 构建虚拟节点环
        for (ServiceMetaInfo serviceMetaInfo : serviceList) {
            for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
                int hash = getHash(serviceMetaInfo.getServiceAddress() + "#" + i);
                virtualNodes.put(hash, serviceMetaInfo);
            }
        }

        // 获取调用请求的 hash 值
        int hash = getHash(requestParams);

        // 选择最接近且大于等于调用请求 hash 值的虚拟节点
        Map.Entry<Integer, ServiceMetaInfo> entry = virtualNodes.ceilingEntry(hash);
        if (entry == null) {
            // 如果没有大于等于调用请求 hash 值的虚拟节点，则返回环首部的节点
            entry = virtualNodes.firstEntry();
        }
        return entry.getValue();
    }

    /**
     * Hash 算法
     *
     * @param key
     * @return
     */
    private int getHash(Object key) {
        return key.hashCode();
    }
}
